/*
 @coding  : utf-8
 @Time    : 2023/5/23 14:50
 @Author  : Rumou
 @File    : 20230523-链表合并.go
 @Description:
*/

// 2.两个升序链表的合并
//
//	2->5->8->10
//	3->4->6->9
//	2->3->4->5->6->8->9->10
package main

import "fmt"

// Node 定义节点结构体
type Node struct {
	data int
	next *Node
}

// LinkedList 定义链表结构体
type LinkedList struct {
	head *Node
}

// Add 增加链表节点元素
func (list *LinkedList) Add(value int) {
	newNode := &Node{data: value}
	if list.head == nil {
		list.head = newNode
	} else {
		currentNode := list.head
		for currentNode.next != nil {
			currentNode = currentNode.next
		}
		currentNode.next = newNode
	}
}

// Print 输出链表
func (list *LinkedList) Print() {
	currentNode := list.head
	for currentNode != nil {
		if currentNode.next != nil {
			fmt.Printf("%v -> ", currentNode.data)
		} else {
			fmt.Printf("%v", currentNode.data)
		}
		currentNode = currentNode.next
	}
	fmt.Println()
}

// Reverse 链表反转
func (list *LinkedList) Reverse() {
	var prevNode *Node
	currentNode := list.head
	for currentNode != nil {
		nextNode := currentNode.next
		currentNode.next = prevNode
		prevNode = currentNode
		currentNode = nextNode
	}
	list.head = prevNode
}

// MergeAndSort 链表合并
func MergeAndSort(list1 *LinkedList, list2 *LinkedList) *LinkedList {
	result := &LinkedList{}
	currentNode1 := list1.head
	currentNode2 := list2.head

	for currentNode1 != nil && currentNode2 != nil {
		if currentNode1.data <= currentNode2.data {
			result.Add(currentNode1.data)
			currentNode1 = currentNode1.next
		} else {
			result.Add(currentNode2.data)
			currentNode2 = currentNode2.next
		}
	}

	for currentNode1 != nil {
		result.Add(currentNode1.data)
		currentNode1 = currentNode1.next
	}

	for currentNode2 != nil {
		result.Add(currentNode2.data)
		currentNode2 = currentNode2.next
	}

	return result
}

func main() {
	list1 := &LinkedList{}
	list1.Add(1)
	list1.Add(2)
	list1.Add(5)

	list2 := &LinkedList{}
	list2.Add(3)
	list2.Add(4)

	fmt.Println("链表1：")
	list1.Print()
	fmt.Println("链表2：")
	list2.Print()

	mergedList := MergeAndSort(list1, list2)
	fmt.Println("合并链表：")
	mergedList.Print()
}
